/*
 * @lc app=leetcode.cn id=92 lang=cpp
 *
 * [92] 反转链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
 public:
  /*ListNode* reverseBetween(ListNode* head, int m, int n) {
  if(!head) return NULL;
  ListNode* hummy= new ListNode(-1);
  hummy->next=head;
  ListNode* ma = hummy;
  ListNode* mc = hummy;
  for(int i =0;i<m-1;i++)
  {
    ma = ma->next;
  }
  for(int i = 0;i<n;i++)
  {
    mc=mc->next;
  }
  ListNode* a = ma->next;
  ListNode* b =a->next;

  ma->next=mc;
  a->next = mc->next;
  // 内部反转链表
  for(;)
  {
    ListNode* c =b->next;
    b->next =a;
    a=b,b=c;
  }

  return hummy->next;

}*/

  /*先内部转再外部转*/
  ListNode* reverseBetween(ListNode* head, int m, int n)
  {
    if (m == n) return head;

    auto dummy = new ListNode(-1);

    dummy->next = head;

    auto a = dummy, d = dummy;

    for (int i = 0; i < m - 1; i++) a = a->next;
    for (int i = 0; i < n; i++) d = d->next;

    auto b = a->next, c = d->next;

    for (auto p = b, q = b->next; q != c;)
    {
      auto o = q->next;
      q->next = p;
      p = q, q = o;
    }

    b->next = c;
    a->next = d;

    return dummy->next;
  }
};
// @lc code=end
